package com.cx.algrithm.sort;

/**
 * @author shkstart
 * @date 7/23/2019 - 3:16 PM
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {4, 1, 6, 52, 0, 19, 11, 0, 5, 13, 32};
        mergeSort2(arr, 0, arr.length - 1);
        for (int v : arr) {
            System.out.println(v);
        }
    }

    public static void mergeSort(int[] a, int start, int end) {
        if (start < end) {//当子序列中只有一个元素时结束递归
            int mid = start + (end - start) / 2;//划分子序列
            mergeSort(a, start, mid);//对左侧子序列进行递归排序
            mergeSort(a, mid + 1, end);//对右侧子序列进行递归排序
            merge(a, start, mid, end);//合并
        }
    }

    //两路归并算法，两个排好序的子序列合并为一个子序列
    public static void merge(int a[], int left, int mid, int right) {
        int tmp[] = new int[a.length];//辅助数组
        int p1 = left, p2 = mid + 1, k = left;//p1、p2是检测指针，k是存放指针

        while (p1 <= mid && p2 <= right) {

            if (a[p1] <= a[p2])
                tmp[k++] = a[p1++];
            else
                tmp[k++] = a[p2++];
        }

        while (p1 <= mid) tmp[k++] = a[p1++];//如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
        while (p2 <= right) tmp[k++] = a[p2++];//同上

        //复制回原素组
        for (int i = left; i <= right; i++)
            a[i] = tmp[i];
    }

    public static void mergeSort2(int[] arr, int startIndex, int endIndex) {
        if (startIndex < endIndex) {
            int mid = startIndex + (endIndex - startIndex) / 2;
            mergeSort2(arr, startIndex, mid);
            mergeSort2(arr, mid + 1, endIndex);
            merge2(arr, startIndex, mid, endIndex);
        }
    }

    private static void merge2(int a[], int left, int mid, int right) {
        int[] tmp = new int[a.length];
        int p1 = left, p2 = mid + 1, k = left;
        while (p1 <= mid && p2 <= right) {
            if (a[p1] <= a[p2]) {
                tmp[k++] = a[p1++];
            } else tmp[k++] = a[p2++];
        }
        while (p1 > mid && p2 <= right) tmp[k++] = a[p2++];
        while (p1 <= mid && p2 > right) tmp[k++] = a[p1++];
        //复制回原素组
        for (int i = left; i <= right; i++)
            a[i] = tmp[i];
    }
}
